package leetcode;

class Solution {
    public boolean canPartition(int[] nums) {
        //先给数组排序
        int[] arr = quick_sort(nums, 0, nums.length - 1);
        //1  3 // 2 2 // 3 1
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j <= i; j++) {
                sum1 += nums[j];
            }
            for (int k = i + 1; k < nums.length; k++) {
                sum2 += nums[k];
            }
            if (sum1 == sum2) {
                return true;
            }
            sum1 = 0;
            sum2 = 0;
        }
        //1 4//2 3 // 3 2 //4 1
        return false;
    }

    public int[] quick_sort(int[] nums, int begin, int end) {
        if (begin > end) {
            return nums;
        }

        int left = begin;
        int right = end;
        int key = begin;

        while (left < right) {
            while (left < right && nums[left] <= nums[key]) {
                left++;
            }
            while (left < right && nums[right] >= nums[key]) {
                right--;
            }
            if (left < right) {
                swap(nums, left, right);
            }
        }
        int meet = left;
        swap(nums, meet, key);
        quick_sort(nums, begin, meet - 1);
        quick_sort(nums, meet + 1, end);
        return nums;
    }

    public void swap(int[] nums, int left, int key) {
        int tmp = nums[left];
        nums[left] = nums[key];
        nums[key] = tmp;
    }
}

public class Test3 {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 5, 11, 5};
        Solution solution = new Solution();
        Boolean ret = solution.canPartition(arr);
        System.out.println(ret);
    }
}
